package puzzle.projecteuler.p200;

import java.math.BigInteger;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

import astudy.util.AdvMath;


public class Problem200B {

	/**
	 * 
     * answer: 229161792008
     * There are 332 number is prime-proof sqube and containing the contiguous 
     * sub-string "200" less than 999999999999, the largest one is 989818872008.
     * 
	 * time cost: 969 ms 
	 * @param args
	 */
	public static void main(String[] args) {
		
		long s = System.currentTimeMillis();

		long MAX = 999999999999L; //12 digits
		Integer[] ps = AdvMath.primes((int)Math.sqrt(MAX/8.0)+1);
		long[] p2 = new long[ps.length];
		for (int i = 0; i < ps.length; i ++) {
			long a = ps[i];
			p2[i] = a*a;
		}
		ps = AdvMath.primes((int)Math.pow(MAX/4.0, 1.0/3.0f)+1);
		long[] q3 = new long[ps.length];
		for (int i = 0; i < ps.length; i ++) {
			long a = ps[i];
			q3[i] = a*a*a;
		}
		
		Set<Long> r = new HashSet<Long>();
		for (int i = 0; i < q3.length; i ++) {
			for (int j = 0; j < p2.length && p2[j] <= MAX/q3[i]; j ++) {
				if (i != j) {
					long n = q3[i]*p2[j];
					String t = String.valueOf(n);
					if (t.indexOf("200") > -1 && !r.contains(n) && isPrimeProof(n)) {
						r.add(n);
						//System.out.println(t + ":" + p2[j] + "*" + q3[i]);
					}
				}
			}
		}
		Long[] rs = r.toArray(new Long[r.size()]);
		Arrays.sort(rs);
		System.out.println("200th: " + rs[199]);
		System.out.println(String.format("There are %d number is prime-proof sqube and containing the contiguous sub-string \"200\" less than %d, the largest one is %d.", rs.length, MAX, rs[rs.length-1]));
		System.out.println((System.currentTimeMillis()-s) + " ms");
	}
	
	private static boolean isPrimeProof(long n) {

		char[] cs = String.valueOf(n).toCharArray();
		for (int i = 0; i < cs.length; i ++) {
			char c = cs[i];
			for (int j = 0; j <= 9; j ++) {
				cs[i] = (char)('0' + j);
				String s = new String(cs);
				BigInteger b = BigInteger.valueOf(Long.valueOf(s));
				if (b.isProbablePrime(64)) {
					return false;
				}
			}
			cs[i] = c;
		}
		return true;
	}
	
}
